Michael Ben-Or
Shafi Goldwasser
ABSTRACT
Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that:
If no faults occur, no set of size t < n/2 of players gets any additional information (other than the function value),
Even if Byzantine faults are allowed, no set of size t < n/3 can either disrupt the computation or get additional information.
Furthermore, the above bounds on t are tight!
- BL.M. Ben-Or and N. Linial, Collective coin flipping, FOCS86.Google Scholar
- CCD.D. Chaum, C. Crepeau and I. Damgard, Multiparty unconditionally secure protocols, These proceedings. Google ScholarDigital Library
- DH.W. Diffie and M. E. Helman, New directions in cryptography, iEEE Trt~ns. Inform. Theory, VoI.IT-22,pp.644-654, 1976.Google Scholar
- DS.D. Dolev and R. St. rong, Polynomial algorithms for multiple processor agreement. STOC82. Google ScholarDigital Library
- FM.P. Fcldlllan and S. Micali, Opt. inlal algoritllrns for Byzantine agreement, These proceediligs.Google Scholar
- GMW1.O. Goldriech, S. Micali and A. Wigderson, Proofs that yield nothing but the validity of the assertion, and a methodology of cryptographic protocol design, FOCS86, pp. 174-187. Google ScholarDigital Library
- GMW2.O. Goldriech, S. Micali and A. Wigderson, How to play any mental game, STOC87, pp. 218-229. Google ScholarDigital Library
- GMR.S. Goldwasser, S. Micali and C. Rackoff, The knowledge complexity of interactive proof systems, STOC85, pp. 291-304. Google ScholarDigital Library
- PSL.M. Pease, R. Shostak and L. Lamport, Reaching agreement in the presence of faults, JACM Vol. 27, pp. 228-234, (1980). Google ScholarDigital Library
- PW.W. W. Peterson and E. J. Weldon, Error correcting codes, Second Ed., MiT Press, (1972).Google Scholar
- Sh.A. Sha!lfir, How to share tt secret, CACM, 22, pp. 612-613, (1979). Google ScholarDigital Library
- Y1.A. C. Yao, How to generate and exchange secrets~ STOC86.Google Scholar
- Y2.A. (2. Yao, On the succession problem for Byzantine Generals, manuscript, (1983).Google Scholar
Index Terms
- Completeness theorems for non-cryptographic fault-tolerant distributed computation
Recommendations
A Fault-Tolerant Systolic Sorter
A fault-tolerant systolic sorter design is proposed. An algorithm-based fault tolerance is achieved by testing the invariants of a systolic sorter during normal operation. Transient and permanent computation errors can be detected by using error-...
Fault Injection and Dependability Evaluation of Fault-Tolerant Systems
The authors describe a dependability evaluation method based on fault injection that establishes the link between the experimental evaluation of the fault tolerance process and the fault occurrence process. The main characteristics of a fault injection ...
Comments